package com.leetcode.根据算法进行分类.动态规划算法相关;

import java.util.ArrayDeque;

/**
 * @author: ZhouBert
 * @date: 2021/3/17
 * @description: 115. 不同的子序列
 * https://leetcode-cn.com/problems/distinct-subsequences/
 * 如果用递归来写回溯的话有个好处：天然的回撤（利用方法体进行的回撤）！
 */
public class C_115_不同的子序列 {

	static C_115_不同的子序列 action = new C_115_不同的子序列();

	public static void main(String[] args) {
//test1();
//		test2();
//		test3();
		//test4();
		test5();
	}

	public static void test1() {
		String s = "rabbbit";
		String t = "rabbit";
		int res = action.numDistinctByForceBackTrack(s, t);
		System.out.println("res = " + res);
	}

	public static void test2() {
		String s = "babgbag";
		String t = "bag";
		int res = action.numDistinctByForceBackTrack(s, t);
		System.out.println("res = " + res);
	}

	public static void test3() {
		String s = "b";
		String t = "b";
		int res = action.numDistinctByForceBackTrack(s, t);
		System.out.println("res = " + res);
	}

	public static void test4() {
		String s = "aabb";
		String t = "abb";
		int res = action.numDistinctByForceBackTrack(s, t);
		System.out.println("res = " + res);
	}

	/**
	 * 54 / 62
	 */
	public static void test5() {
		//700531452
		String s = "adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcddcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc";
		String t = "bcddceeeebecbc";
		long start = System.currentTimeMillis();
		//暴力回溯的答案是对的，本地耗时 34 s
		int res = action.numDistinctByForceBackTrack(s, t);
		System.out.println("res = " + res + ";cost:" + (System.currentTimeMillis() - start));
	}


	/**
	 * 如果看成分割 t 串的问题，那就应该可以用 回溯来解决
	 * 从回溯的步骤来看，确实存在重复计算，先做暴力回溯，暂时没有很好的想法来解决重复计算的问题！
	 * --
	 * 没想到 54 / 62 就超时了，那么如何进行优化呢？
	 * --
	 * 回顾了一下，有三个地方进行回溯
	 * --
	 * 为啥我写得出来的回溯不是递归版本的？看来我的回溯还是需要再加强下！
	 * 看了下题解，都是在 test5 时超时
	 *
	 * @param s
	 * @param t
	 * @return
	 */
	public int numDistinctByForceBackTrack(String s, String t) {
		char[] sChars = s.toCharArray();
		char[] tChars = t.toCharArray();
		int lenS = sChars.length;
		int lenT = tChars.length;
		int tEndIndex = lenT - 1;
		int sEndIndex = lenS - 1;
		int res = 0;
		//记录 s 中已经确认匹配的索引
		ArrayDeque<Integer> deque = new ArrayDeque<>(lenT);
		int ti = 0;
		for (int si = 0; si < lenS; si++) {
			if (sChars[si] == tChars[ti]) {
				//如果匹配
				if (ti == tEndIndex) {
					//已经匹配完毕
					res++;
					//BackTrack 1
					if (si == sEndIndex) {
						//s 串 如果已经到达末尾了
						if (deque.isEmpty()) {
							//当栈为空，说明已经回撤到底了，可以退出循环
							break;
						}
						Integer tempIndex = deque.removeLast();
						si = tempIndex;
						ti--;
					}

				} else {
					//此时即使 ti 没有匹配到末尾

					//BUG 修复
					//如果此时 si 走到了末尾，说明这次遍历失败，那么仍然需要回撤
					//BackTrack 2
					if (si == sEndIndex) {
						//s 串 如果已经到达末尾了
						if (deque.isEmpty()) {
							break;
						}
						Integer tempIndex = deque.removeLast();
						si = tempIndex;
						ti--;
					} else {
						deque.addLast(si);
						ti++;
					}

				}
			} else {
				//此时即使没有匹配到，但是 si 走到了末尾，本次是失败的遍历，那么仍然需要回撤

				//BackTrack 3
				if (si == sEndIndex) {
					//s 串 如果已经到达末尾了
					if (deque.isEmpty()) {
						break;
					}
					Integer tempIndex = deque.removeLast();
					si = tempIndex;
					ti--;
				}
			}
		}
		return res;
	}

	/**
	 * dp[t.length() + 1][s.length() + 1] : dp[i][j]代表t[0-i]在s[0-j]中的出现的次数
	 * 如果某一位t[i]==s[j]，则此时的次数=dp[i-1][j-1]+dp[i][j-1]
	 * 如果某一位t[i]!=s[j]，则此时的次数=dp[i][j-1]
	 * https://leetcode-cn.com/problems/distinct-subsequences/solution/115-bu-tong-de-zi-xu-lie-java-hui-su-dong-tai-gui-/
	 *
	 * @param s
	 * @param t
	 * @return
	 */
	public int numDistinctByDP(String s, String t) {
		int tLen = t.length();
		int sLen = s.length();
		char[] sChars = s.toCharArray();
		char[] tChars = t.toCharArray();

		int[][] dp = new int[tLen + 1][sLen + 1];
		for (int j = 0; j <= sLen; j++) {
			dp[0][j] = 1;
		}
		for (int i = 1; i <= tLen; i++) {
			for (int j = 1; j <= sLen; j++) {
				if (tChars[i - 1] == sChars[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
				} else {
					dp[i][j] = dp[i][j - 1];
				}
			}
		}
		return dp[tLen][sLen];

	}

	/**
	 * 我的关于 DP 的理解。
	 * 其实从 回溯 到 DP 是不太好想到的，不容易具象到如此的动态方程。可能跟我写的是循环而不是递归有关系。
	 * 仔细琢磨一下，当我进行回撤的时候：（对于 tChars sChars）
	 * 我想要快速知道 tChars[eIndex-1] 在 sChars 中的下一个位置在哪里；
	 * -> 可以对每一个 it,is 进行标记 dp[it][is] 表示 tChars[it] 在 sChars[is] 中的子序列个数。
	 * -> 假设上述实现，那么结果就是 dp[itEndIndex][isEndIndex] ,只需要找到状态转移方程，就能取代回溯！
	 * -> 对于状态转移方程：
	 * if(tChars[it]==sChars[is]) ,dp[it][is]=当 tChars[it-1]==sChars[is-1] 时的值 + 无关本条件时的情况
	 * 即 dp[it-1][is-1] + dp[it][is-1];
	 * if(tChars[it]!=sChars[is]) ,dp[it][is] = 无关本条件时的情况 即  dp[it][is-1]。
	 * --
	 * 至此，框架已经搭好了，看看具体的细节：
	 * 【由于 base case:dp[0-1][0-1] 不符合规范，那么需要创建一个 dp[tLen+1][sLen+1] 的数组】
	 * 那么此时 dp[i][j] 表示的是 tChars[i-1] 在 sChars[j-1] 中的子序列个数
	 * 那么 base case:dp[0][0] 表示的是：空串在空串中的子序列个数
	 * 于是初始就出来了
	 * （s:babgbag,t:bag)
	 * T(i)/S(j) "" b a b g b a g
	 *    ""     1 1 1 1 1 1 1 1
	 *    b      0
	 *    a      0
	 *    g      0
	 * 那么 dp[1][1] = dp[0][0] + dp[1][0] = 1+0=1;
	 * 以此类推。
	 * @param s
	 * @param t
	 * @return
	 */
	public int numDistinctByDPAfterUnderstanding(String s, String t){
		int tLen = t.length();
		int sLen = s.length();
		char[] sChars = s.toCharArray();
		char[] tChars = t.toCharArray();

		int[][] dp = new int[tLen + 1][sLen + 1];
		for (int j = 0; j <= sLen; j++) {
			dp[0][j] = 1;
		}
		for (int i = 1; i <= tLen; i++) {
			for (int j = 1; j <= sLen; j++) {
				if (tChars[i - 1] == sChars[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
				} else {
					dp[i][j] = dp[i][j - 1];
				}
			}
		}
		return dp[tLen][sLen];
	}
}
